package leetcode.editor.cn;

public class _148_SortList {
    public static void main(String[] args) {
        Solution solution = new _148_SortList().new Solution();
        ListNode a4 = new _148_SortList().new ListNode(3);
        ListNode a3 = new _148_SortList().new ListNode(1, a4);
        ListNode a2 = new _148_SortList().new ListNode(2, a3);
        ListNode a1 = new _148_SortList().new ListNode(4, a2);
        solution.sortList(a1);

    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 自顶向下递归
    class Solution {
        public ListNode sortList(ListNode head) {
            return sortList(head, null); // 注意这是左闭右开的
        }

        public ListNode sortList(ListNode head, ListNode tail) {
            if (head == null) return head;
            if (head.next == tail) {
                head.next = null;  // 注意这里需要断开连接
                return head;
            }
            ListNode fast = head, slow = head;
            while (fast.next != tail && fast.next.next != tail) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode mid = slow.next;
            ListNode l1 = sortList(head, mid);
            ListNode l2 = sortList(mid, tail);
            return merge(l1, l2);
        }


        private ListNode merge(ListNode l1, ListNode l2) {
            if (l1 == null && l2 == null) {
                return null;
            }
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            if (l1.val < l2.val) {
                l1.next = merge(l1.next, l2);
                return l1;
            } else {
                l2.next = merge(l1, l2.next);
                return l2;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}